﻿using System;

using System.Collections.Generic;
using System.Text;

namespace Silvermoon.Windows
{
    /// <summary>
    /// DblLinkedList contains a chain of <see cref="DblLinkedNode"/>s.
    /// DblLinkedList is a cyclic chain. The very first and very last node is always <paramref name="End"/> where End's Previous and Next initially point to itself.
    /// A cyclic list is easier to maintain addings and removes, since there is no special check for the endings required.
    /// The advantage of a double linked list against an array list is the fact that it performs faster for inserts or removals at positions other than the near end of the array.
    /// Disadvantage is the fact that it requires more space (3 times) than a simple list, but still less than a dictionary.
    /// </summary>
    /// <typeparam name="T">Type of value to maintain.</typeparam>
    public class DblLinkedList<T> : IEnumerable<T>
    {
        private DblLinkedNode<T> node;

        /// <summary>
        /// Gets the node that marks the end both at the top and the bottom.
        /// </summary>
        public DblLinkedNode<T> End { get { return node; } }

        /// <summary>
        ///  Gets the last node in the chain, otherwise End.
        /// </summary>
        public DblLinkedNode<T> Last { get { return node.Previous; } }

        /// <summary>
        /// Gets the first node in the chain, otherwise End.
        /// </summary>
        public DblLinkedNode<T> First { get { return node.Next; } }

        public DblLinkedList()
            : base()
        {
            node = new DblLinkedNode<T>();
            node.Previous = node.Next = node;
        }

        /// <summary>
        /// Gets whether the list is empty.
        /// </summary>
        public bool IsEmpty
        {
            get { return node == node.Next; }
        }

        /// <summary>
        /// Adds a node at the head of the chain.
        /// </summary>
        /// <param name="value">Value for the node.</param>
        /// <returns>DblLinkedNode.</returns>
        public DblLinkedNode<T> AddFirst(T value)
        {
            var node = new DblLinkedNode<T>(value);
            this.node.Add(node);
            return node;
        }

        /// <summary>
        /// Adds a node at the tail of the chain.
        /// </summary>
        /// <param name="value">Value for the node.</param>
        /// <returns>DblLinkedNode.</returns>
        public DblLinkedNode<T> AddLast(T value)
        {
            var node = new DblLinkedNode<T>(value);
            this.Last.Add(node);
            return node;
        }

        /// <summary>
        /// Inserts  a node after another node.
        /// </summary>
        /// <param name="node">Node after to add.</param>
        /// <param name="value">Value for the node.</param>
        /// <returns>DblLinkedNode.</returns>
        public DblLinkedNode<T> InsertAfter(DblLinkedNode<T> node, T value)
        {
            var newNode = new DblLinkedNode<T>(value);
            node.Add(newNode);
            return newNode;
        }

        /// <summary>
        /// Removes a node from chain.
        /// </summary>
        /// <param name="node">Node to remove.</param>
        public void Remove(DblLinkedNode<T> node)
        {
            node.Remove();
        }

        /// <summary>
        /// Clears the list.
        /// </summary>
        public void Clear()
        {
            End.Next = End.Previous = End;
        }

        /// <summary>
        /// Finds the node for a value.
        /// </summary>
        /// <param name="value">Value of the node.</param>
        /// <returns>DblLinkedNode, otherwise null.</returns>
        public DblLinkedNode<T> FindNode(T value)
        {
            DblLinkedNode<T> end = this.End;
            DblLinkedNode<T> node = end.Next;
            while (node != end)
            {
                if (node.Value.Equals(value)) return node;
                node = node.Next;
            }
            return null;
        }

        /// <summary>
        /// Removes a value from chain.
        /// </summary>
        /// <param name="value">Value to remove.</param>
        public void Remove(T value)
        {
            var node = FindNode(value);
            if (node != null) node.Remove();
        }

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this.First, this.End);
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class Enumerator : IEnumerator<T>
        {
            private DblLinkedNode<T> first;
            private DblLinkedNode<T> end;
            private DblLinkedNode<T> current;

            public Enumerator(DblLinkedNode<T> first, DblLinkedNode<T> end)
                : base()
            {
                this.first = first;
                this.end = end;
                this.current = end;
            }

            #region IEnumerator<T> Members

            public T Current
            {
                get { return current.Value; }
            }

            #endregion

            #region IDisposable Members

            public void Dispose()
            {
            }

            #endregion

            #region IEnumerator Members

            object System.Collections.IEnumerator.Current
            {
                get { return current; }
            }

            public bool MoveNext()
            {
                current = current.Next;
                return current != end;
            }

            public void Reset()
            {
                current = first.Previous;
            }

            #endregion
        }

        #endregion

    }
}
